package arithmetic2.day12;

import java.util.ArrayList;
import java.util.List;

/*
    求一个树的最大快乐值
 */
public class Empolyee {
    public int happy;   //该员工的快乐值
    public List<Empolyee> nexts; //该员工的所有直接下属

    public Empolyee(int happy) {
        this.happy = happy;
        this.nexts = new ArrayList<>();
    }

    public Empolyee(int happy, List<Empolyee> nexts) {
        this.happy = happy;
        this.nexts = nexts;
    }

    public void add(Empolyee empolyee){
        nexts.add(empolyee);
    }

    public int maxHappy(){
        Info info = process(this);
        return Math.max(info.laiMaxHappy,info.buMaxHappy);
    }

    public Info process(Empolyee empolyee){
        if(empolyee.nexts.size()==0){
            return new Info(empolyee.happy,0);
        }
        //当前员工来
        int laiMaxHappy = empolyee.happy;
        //当前员工不来
        int buMaxHappy = 0;
        for(Empolyee emp : empolyee.nexts){
            Info info = process(emp);
            //当前员工来的时候直接下属不来
            laiMaxHappy += info.buMaxHappy;
            //当前员工不来的时候直接下属可以来，也可以不来
            buMaxHappy += Math.max(info.laiMaxHappy,info.buMaxHappy);
        }
        return new Info(laiMaxHappy,buMaxHappy);
    }

    public static class Info{
        public int laiMaxHappy;
        public int buMaxHappy;

        public Info(int laiMaxHappy, int buMaxHappy) {
            this.laiMaxHappy = laiMaxHappy;
            this.buMaxHappy = buMaxHappy;
        }
    }

    public static void main(String[] args) {
        Empolyee emp1 = new Empolyee(10);
        Empolyee emp2 = new Empolyee(3);
        Empolyee emp3 = new Empolyee(20);
        Empolyee emp4 = new Empolyee(40);
        Empolyee emp5 = new Empolyee(60);
        Empolyee emp6 = new Empolyee(3);
        Empolyee emp7 = new Empolyee(5);
        Empolyee emp8 = new Empolyee(6);
        emp1.add(emp2);
        emp1.add(emp3);
        emp1.add(emp4);
        emp2.add(emp5);
        emp3.add(emp6);
        emp4.add(emp7);
        emp4.add(emp8);
        int maxHappy = emp1.maxHappy();
        System.out.println(maxHappy);
    }
}
